<!DOCTYPE html>
<html lang="en">

<!-- Head tag -->
<head>
    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="google-site-verification" content="xBT4GhYoi5qRD5tr338pgPM5OWHHIDR6mNg1a3euekI" />
    <meta name="viewport" content="width=device-width, initial-scale=1">
    <meta name="description" content="">
    <meta name="keyword"  content="">
    <link rel="shortcut icon" href="/img/logo.png">
    <!-- Place this tag in your head or just before your close body tag. -->
    <script async defer src="https://buttons.github.io/buttons.js"></script>
    <title>
        
          卡诺图与“只出现一次的数字”问题 - 宋正兵的博客 | zbsong Blog
        
    </title>

    <link rel="canonical" href="zbsong.top/article/卡诺图与“只出现一次的数字”问题/">

    <!-- Bootstrap Core CSS -->
    <link rel="stylesheet" href="/css/bootstrap.min.css">

    <!-- Custom CSS --> 
    <link rel="stylesheet" href="/css/beantech.min.css">

    <link rel="stylesheet" href="/css/donate.css">
    
    <!-- Pygments Highlight CSS -->
    <link rel="stylesheet" href="/css/highlight.css">

    <link rel="stylesheet" href="/css/widget.css">

    <link rel="stylesheet" href="/css/rocket.css">

    <link rel="stylesheet" href="/css/signature.css">

    <link rel="stylesheet" href="/css/toc.css">

    <!-- Custom Fonts -->
    <!-- <link href="https://maxcdn.bootstrapcdn.com/font-awesome/4.3.0/css/font-awesome.min.css" rel="stylesheet" type="text/css"> -->
    <!-- Hux change font-awesome CDN to qiniu -->
    <link href="https://cdn.staticfile.org/font-awesome/4.5.0/css/font-awesome.min.css" rel="stylesheet" type="text/css">


    <!-- Hux Delete, sad but pending in China
    <link href='http://fonts.googleapis.com/css?family=Lora:400,700,400italic,700italic' rel='stylesheet' type='text/css'>
    <link href='http://fonts.googleapis.com/css?family=Open+Sans:300italic,400italic,600italic,700italic,800italic,400,300,600,700,800' rel='stylesheet' type='text/
    css'>
    -->


    <!-- HTML5 Shim and Respond.js IE8 support of HTML5 elements and media queries -->
    <!-- WARNING: Respond.js doesn't work if you view the page via file:// -->
    <!--[if lt IE 9]>
        <script src="https://oss.maxcdn.com/libs/html5shiv/3.7.0/html5shiv.js"></script>
        <script src="https://oss.maxcdn.com/libs/respond.js/1.4.2/respond.min.js"></script>
    <![endif]-->

    <!-- ga & ba script hoook -->
    <script></script>
</head>


<!-- hack iOS CSS :active style -->
<body ontouchstart="">
	<!-- Modified by Yu-Hsuan Yen -->
<!-- Post Header -->
<style type="text/css">
    header.intro-header{
        
            background-image: url('https://api.dujin.org/bing/1920.php')
            /*post*/
        
    }
    
</style>

<header class="intro-header" >
    <!-- Signature -->
    <div id="signature">
        <div class="container">
            <div class="row">
                <div class="col-lg-8 col-lg-offset-2 col-md-10 col-md-offset-1">
                
                    <div class="post-heading">
                        <div class="tags">
                            
                              <a class="tag" href="/tags/#algorithm" title="algorithm">algorithm</a>
                            
                        </div>
                        <h1>卡诺图与“只出现一次的数字”问题</h1>
                        <!-- <h2 class="subheading">卡诺图在“只出现一次的数字”问题的应用</h2> -->
                        <span class="meta">
                            宋正兵 on
                            2020-12-11
                        </span>
                    </div>
                


                </div>
            </div>
        </div>
    </div>
</header>

    <!-- Navigation -->
<nav class="navbar navbar-default navbar-custom navbar-fixed-top">
    <div class="container-fluid">
        <!-- Brand and toggle get grouped for better mobile display -->
        <div class="navbar-header page-scroll">
            <button type="button" class="navbar-toggle">
                <span class="sr-only">Toggle navigation</span>
                <span class="icon-bar"></span>
                <span class="icon-bar"></span>
                <span class="icon-bar"></span>
            </button>
            <a class="navbar-brand" href="/">songzblink</a>
        </div>

        <!-- Collect the nav links, forms, and other content for toggling -->
        <!-- Known Issue, found by Hux:
            <nav>'s height woule be hold on by its content.
            so, when navbar scale out, the <nav> will cover tags.
            also mask any touch event of tags, unfortunately.
        -->
        <div id="huxblog_navbar">
            <div class="navbar-collapse">
                <ul class="nav navbar-nav navbar-right">
                    <li>
                        <a href="/">主页</a>
                    </li>
					<li>
                        <a href="/archive/">归档</a>
                    </li>
					<li>
                        <a href="/tags/">标签</a>
                    </li>
					<li>
                        <a href="/about/">关于</a>
                    </li>
					<!--
					修改about在前面的问题
                    
                        
                    
                        
                        <li>
                            <a href="/about/">关于</a>
                        </li>
                        
                    
                        
                        <li>
                            <a href="/archive/">归档</a>
                        </li>
                        
                    
                        
                        <li>
                            <a href="/tags/">标签</a>
                        </li>
                        
                    
                    -->
                </ul>
            </div>
        </div>
        <!-- /.navbar-collapse -->
    </div>
    <!-- /.container -->
</nav>
<script>
    // Drop Bootstarp low-performance Navbar
    // Use customize navbar with high-quality material design animation
    // in high-perf jank-free CSS3 implementation
    var $body   = document.body;
	// querySelector 获取文档中 id="demo" 的元素
    var $toggle = document.querySelector('.navbar-toggle');
    var $navbar = document.querySelector('#huxblog_navbar');
    var $collapse = document.querySelector('.navbar-collapse');

    $toggle.addEventListener('click', handleMagic)
    function handleMagic(e){
        if ($navbar.className.indexOf('in') > 0) {
        // CLOSE
            $navbar.className = " ";
            // wait until animation end.
            setTimeout(function(){
                // prevent frequently toggle
                if($navbar.className.indexOf('in') < 0) {
                    $collapse.style.height = "0px"
                }
            },400)
        }else{
        // OPEN
            $collapse.style.height = "auto"
            $navbar.className += " in";
        }
    }
</script>


    <!-- Main Content -->
    <!-- Modify by Yu-Hsuan Yen -->

<!-- Post Content -->
<article>
    <div class="container">
        <div class="row">

            <!-- Post Container -->
            <div class="
                col-lg-8 col-lg-offset-2
                col-md-10 col-md-offset-1
                post-container">

				
                <h2 id="只出现一次的数字问题">只出现一次的数字问题</h2>
<h3 id="只出现一次的数字-ii">只出现一次的数字 II</h3>
<blockquote>
<p>给定一个<strong>非空</strong>整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。</p>
</blockquote>
<p>题目来源：<a href="https://leetcode-cn.com/problems/single-number-ii/" target="_blank" rel="noopener">LeetCode</a></p>
<h4 id="卡诺图解法">卡诺图解法</h4>
<blockquote>
<p>如果不理解卡诺图，可以看下面的<a href="#jump">卡诺图章节</a></p>
</blockquote>
<p>根据题目，我们需要找到一个能表达一个模 <code>3</code> 含义的状态转移过程，需要设置两个状态位来描述 <code>00-&gt;01-&gt;10-&gt;00</code> 的状态转移过程。</p>
<p>状态转移矩阵，其中 <code>a</code>、<code>b</code> 代表状态位的低位和高位，每一个状态由 <code>a</code>、<code>b</code> 和到来的 bit 位 <code>x</code> 决定。</p>
<p><img src="https://pic.tyzhang.top/images/2020/12/11/9365eb6b82ff445789f100c8cbba982a.png" alt="9365eb6b82ff445789f100c8cbba982a.png"></p>
<p>此时并没有办法直接通过观察看出我们所需要执行操作的具体形式，此时可以祭出卡诺图来解决问题。</p>
<p>下面是关于 <code>b</code> 的卡诺图，表中的数位对应状态的下一个状态中 <code>b</code> 的值。</p>
<p><img src="https://pic.tyzhang.top/images/2020/12/11/Snipaste_2020-12-11_18-01-55.png" alt="Snipaste_2020-12-11_18-01-55.png"></p>
<p>使用卡诺图化简法，不难写出如下转移方程：<br>
$$<br>
b = \overline{x}\overline{a}b + x\overline{a}\overline{b} = \overline{a}(\overline{x}b + x\overline{b})<br>
$$<br>
又由于 $\overline{x}b + x\overline{b} = x  \bigoplus b $ ，所以有 <code>b = ~a &amp; (b ^ x)</code>。</p>
<p>下面是关于 <code>a</code> 的卡诺图，表中的数位对应状态的下一个状态中 <code>a</code> 的值。</p>
<p><img src="https://pic.tyzhang.top/images/2020/12/11/Snipaste_2020-12-11_18-01-45.png" alt="Snipaste_2020-12-11_18-01-45.png"></p>
<p>使用卡诺图化简法，不难写出如下转移方程：<br>
$$<br>
a = \overline{x}a + xb<br>
$$<br>
所以有 <code>a = (~x &amp; a) | (x &amp; b)</code>。</p>
<p>把所有数依次输入，然后不断更新状态.最终，出现 <code>3</code> 次的位都成 <code>0</code>（也就是<code>00</code>），出现 <code>1</code> 次的位都成了 <code>1</code>（也就是 <code>01</code>）。我们最后直接返回状态 <code>Y</code> 就是要的答案。（另外辅助验证，最后 <code>X</code> 应该为全 <code>0</code> ，因为最后所有位的状态要么是 <code>00</code> ，即出现 <code>3</code> 次的数的位，要么是 <code>01</code>，即出现 <code>1</code> 次的数的位）</p>
<p>可以写出代码为：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">singleNumber</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> a = <span class="number">0</span>, b = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">int</span> tmp;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> x : nums) &#123;</span><br><span class="line">            tmp = b;</span><br><span class="line">            b = ~a &amp; (x ^ b);</span><br><span class="line">            a = (~x &amp; a) | (x &amp; tmp);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> b;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>由于代码中是先计算 <code>b</code> 再计算 <code>a</code> 的，所以可以通过画一个关于 <code>a</code>、<code>new_b</code> 和 <code>x</code> 的卡诺图来利用先生成的 <code>new_b</code>。</p>
<p><img src="https://pic.tyzhang.top/images/2020/12/11/Snipaste_2020-12-11_18-30-34.png" alt="Snipaste_2020-12-11_18-30-34.png"></p>
<p>有 $a = x\overline{a}\overline{b} +  \overline{x}a\overline{b} = (x\overline{a} + \overline{x}a)\overline{b}$ ，很明显的异或操作，于是有 <code>a = ~b &amp; (x ^ a)</code> 。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">singleNumber</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> a = <span class="number">0</span>, b = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> x : nums) &#123;</span><br><span class="line">            b = ~a &amp; (x ^ b);</span><br><span class="line">            a = ~b &amp; (x ^ a);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> b;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="逻辑真值表达式解法">逻辑真值表达式解法</h4>
<p>同样的是需要找到一种逻辑操作，可以满足 <code>1 * 1 * 1 = 0</code> 且 <code>0 * 1 = 1 * 0 = 1</code>，其中 <code>*</code> 是这种新逻辑操作符。设当前状态为 <code>XY</code>，输入为 <code>Z</code>，那么我们可以为<code>X</code> 和 <code>Y</code> 列出真值表。</p>
<table>
<thead>
<tr>
<th style="text-align:center">XY</th>
<th style="text-align:center">Z</th>
<th style="text-align:center">x$_{NEW}$</th>
<th style="text-align:center">y$_{NEW}$</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center">00</td>
<td style="text-align:center">0</td>
<td style="text-align:center">0</td>
<td style="text-align:center">0</td>
</tr>
<tr>
<td style="text-align:center">01</td>
<td style="text-align:center">0</td>
<td style="text-align:center">0</td>
<td style="text-align:center">1</td>
</tr>
<tr>
<td style="text-align:center">10</td>
<td style="text-align:center">0</td>
<td style="text-align:center">1</td>
<td style="text-align:center">0</td>
</tr>
<tr>
<td style="text-align:center">00</td>
<td style="text-align:center">1</td>
<td style="text-align:center">0</td>
<td style="text-align:center">1</td>
</tr>
<tr>
<td style="text-align:center">01</td>
<td style="text-align:center">1</td>
<td style="text-align:center">1</td>
<td style="text-align:center">0</td>
</tr>
<tr>
<td style="text-align:center">10</td>
<td style="text-align:center">1</td>
<td style="text-align:center">0</td>
<td style="text-align:center">0</td>
</tr>
</tbody>
</table>
<p>对于 <code>Y</code>，转化为逻辑表达式就是（取所有 $Y_{NEW} = 1$ 的行的 <code>X</code>、<code>Y</code>、<code>Z</code> 的最小项，然后 $OR$ 起来）。</p>
<p>$$<br>
Y_{NEW} = \overline{X}Y\overline{Z} + \overline{X}\overline{Y}Z<br>
$$<br>
化简：<br>
$$<br>
Y_{NEW} = \overline{X}(Y \bigoplus  Z)<br>
$$<br>
同理可以求得 <code>X</code> 的逻辑表达式，此处有一个可以取巧的地方，不用再去求新的表达式。我们更新完 <code>Y</code> 之后，把 $Y_{NEW}$ 放到逻辑表达式中替换原来的 <code>Y</code> 的值形成新的逻辑表，这个新的逻辑表（<code>Z</code>、$X_{NEW}$、$XY_{NEW}$）对于 <code>X</code> 来说是跟求 <code>Y</code> 的时候的逻辑表是同构的。</p>
<table>
<thead>
<tr>
<th style="text-align:center">Xy</th>
<th style="text-align:center">Z</th>
<th style="text-align:center">x$_{NEW}$</th>
<th style="text-align:center">y$_{NEW}$</th>
<th style="text-align:center">Xy$_{NEW}$</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center">00</td>
<td style="text-align:center">0</td>
<td style="text-align:center">0</td>
<td style="text-align:center">0</td>
<td style="text-align:center">00</td>
</tr>
<tr>
<td style="text-align:center">01</td>
<td style="text-align:center">0</td>
<td style="text-align:center">0</td>
<td style="text-align:center">1</td>
<td style="text-align:center">01</td>
</tr>
<tr>
<td style="text-align:center">10</td>
<td style="text-align:center">0</td>
<td style="text-align:center">1</td>
<td style="text-align:center">0</td>
<td style="text-align:center">10</td>
</tr>
<tr>
<td style="text-align:center">00</td>
<td style="text-align:center">1</td>
<td style="text-align:center">0</td>
<td style="text-align:center">1</td>
<td style="text-align:center">00</td>
</tr>
<tr>
<td style="text-align:center">01</td>
<td style="text-align:center">1</td>
<td style="text-align:center">1</td>
<td style="text-align:center">0</td>
<td style="text-align:center">01</td>
</tr>
<tr>
<td style="text-align:center">10</td>
<td style="text-align:center">1</td>
<td style="text-align:center">0</td>
<td style="text-align:center">0</td>
<td style="text-align:center">10</td>
</tr>
</tbody>
</table>
<p>所以 $X_{NEW} = \overline{Y_{NEW}}(X \bigoplus  Z)$</p>
<p>把所有数依次输入，然后不断更新状态.最终，出现 <code>3</code> 次的位都成 <code>0</code>（也就是<code>00</code>），出现 <code>1</code> 次的位都成了 <code>1</code>（也就是 <code>01</code>）。我们最后直接返回状态 <code>Y</code> 就是要的答案。（另外辅助验证，最后 <code>X</code> 应该为全 <code>0</code> ，因为最后所有位的状态要么是 <code>00</code> ，即出现 <code>3</code> 次的数的位，要么是 <code>01</code>，即出现 <code>1</code> 次的数的位）</p>
<p>代码</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">singleNumber</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> a = <span class="number">0</span>, b = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> x : nums) &#123;</span><br><span class="line">            b = ~a &amp; (x ^ b);</span><br><span class="line">            a = ~b &amp; (x ^ a);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> b;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="卡诺图"><span id="jump">卡诺图</span></h2>
<h3 id="关于最小项">关于“最小项”</h3>
<h4 id="1最小项的定义">（1）最小项的定义</h4>
<p>如果一个函数的某个乘积项<strong>包含了函数的全部变量</strong>，其中<strong>每个变量</strong>都以<strong>原变量或反变量的形式</strong>出现，且<strong>仅出现一次</strong>，则这个乘积项称为该函数的一个标准积项，通常成为<strong>最小项</strong>。</p>
<p>例如 <code>3</code> 个变量 A、B 、C 可组成 <code>8</code> 个 最小项：<br>
$$<br>
\overline{A}\overline{B}\overline{C}、\overline{A}\overline{B}C、\overline{A}B\overline{C}、A\overline{B}\overline{C}、\overline{A}BC、A\overline{B}C、AB\overline{C}、ABC<br>
$$</p>
<h4 id="2最小项的表示方法">（2）最小项的表示方法</h4>
<p>通常用符号 $m_{i}$ 来表示最小项。下标 <code>i</code> 的确定：把最小项中的原变量标记为 <code>1</code>，反变量标记为 <code>0</code>，当变量顺序确定后，可以按顺序排列成一个二进制数，则与这个二进制数相对应的十进制数，就是这个最小项的下标 <code>i</code>。</p>
<p><code>3</code> 个变量 A、B、C 的 <code>8</code> 个最小项可以分别表示为：<br>
$$<br>
m_{0}=\overline{A}\overline{B}\overline{C}、m_{1}=\overline{A}\overline{B}C、m_{2}=\overline{A}B\overline{C}、m_{3}=\overline{A}BC、m_{4}=A\overline{B}\overline{C}、m_{5}=A\overline{B}C、m_{6}=AB\overline{C}、m_{7}=ABC<br>
$$</p>
<h4 id="3最小项的性质">（3）最小项的性质</h4>
<p><img src="https://pic.tyzhang.top/images/2020/12/11/image-20201211110655988.png" alt="image-20201211110655988.png"></p>
<ul>
<li>性质1：任意一个最小项，只有一组变量取值使其值为 <code>1</code>，而在变量取其他各组值时这个最小项的值都是 <code>0</code>；</li>
<li>性质2：不同的最小项，使它的值为 <code>1</code> 的那一组变量取值也不同；</li>
<li>性质3：任意两个不同的最小项的乘积必为 <code>0</code>；</li>
<li>性质4：全部最小项的和必为 <code>1</code>；</li>
</ul>
<h4 id="4逻辑函数的最小项表达式">（4）逻辑函数的最小项表达式</h4>
<p>任何一个逻辑函数都可以表示成唯一的一组最小项之和，称为标准与或表达式，也称为最小项表达式。</p>
<p>对于不是最小项表达式的与或表达式，可以利用公式进行化简。</p>
<h4 id="5公式和定理">（5）公式和定理</h4>
<p>交换律：$A B = B  A \ A + B = B + A$</p>
<p>结合律：$(A B)C = A (B C) \ (A+B)+C = A+(B+C)$<br>
分配律：$A(B+C) = AB + AC \ A + BC = (A+B)(A+C)$</p>
<p>同一律：$AA=A \ A+A=A$</p>
<p>德·摩根定律：$\overline{AB} = \overline{A} + \overline{B} \ \overline{A+B}=\overline{A} \cdot \overline{B}$</p>
<p>还原律：$\overline{\overline{A}} = A$</p>
<h4 id="6最小项的相邻性">（6）最小项的相邻性</h4>
<p>任何两个最小项如果他们只有一个因子不同，其余因子都相同，则称这两个最小项为相邻最小项。</p>
<p>显然，$m_{0}(\overline{A}\overline{B}\overline{C})$  与 $m_{1}(\overline{A}\overline{B}C)$  具有相邻性，而 $m_{1}(\overline{A}\overline{B}C)$ 与 $m_{2}(\overline{A}B\overline{C})$ 不相邻。</p>
<p>相邻的两个最小项之和可以合并成一项，并消去一个变量。如：<br>
$$<br>
m_{0} + m_{2} = \overline{A}\overline{B}\overline{C} + \overline{A}B\overline{C} = \overline{A}(\overline{AB})m_{0} + m_{2} = \overline{A}\overline{B}\overline{C} + \overline{A}B\overline{C} = \overline{A}(\overline{B}+B)\overline{C} = \overline{A}\overline{C}<br>
$$</p>
<h3 id="卡诺图的构成">卡诺图的构成</h3>
<p>把所有最小项按一定顺序排列起来，每一个小方格由一个最小项占有。设变量数为 n，则最小项的数目为 $2^{n}$。两个变量的卡诺图：</p>
<p><img src="https://pic.tyzhang.top/images/2020/12/11/Snipaste_2020-12-11_16-02-21.png" alt="Snipaste_2020-12-11_16-02-21.png"></p>
<p>上图还显示这些小方格与变量 <code>A</code> 和变量 <code>B</code> 之间的关系。每行、列都被表上 <code>0</code>、<code>1</code> 代表变量值。</p>
<p><img src="https://pic.tyzhang.top/images/2020/12/11/Snipaste_2020-12-11_16-14-20.png" alt="Snipaste_2020-12-11_16-14-20.png"></p>
<p>如上图，其中有三个小方格被标上 <code>1</code>，这些方格就代表了函数的最小项：<br>
$$<br>
m_{1} + m_{2} + m_{3} = \overline{A}B + A\overline{B} + AB = A + B<br>
$$<br>
<strong>注意：</strong></p>
<p>最小项并不是按照自然二进制顺序排列，而是按照类似于格雷码的顺序排列，这种排列方式相邻两列只有一位发生变化。</p>
<h3 id="逻辑函数的卡诺图化简法">逻辑函数的卡诺图化简法</h3>
<p>卡诺图相邻性的特点保证了<strong>几何相邻两方格所代表的最小项只有一个变量不同</strong>。因此，若相邻的方格都为 <code>1</code> 时，则对应的最小项就可以合并。合并的结果是消去这个不同的变量，只保留相同的变量。这是图形化简法的依据。</p>
<p>性质：在 <code>n</code> 个变量的卡诺图中，若有 <code>2k</code> 个 <code>1</code> 格相邻（即圈内的 <code>1</code> 格数必须为 <code>1,2,4,8</code> 等，它们可以圈在一起加以合并，合并时可消去 <code>k</code> 个不同的变量，简化为一个具有 <code>(n-k)</code> 个变量的与项。若 <code>k=n</code>，则合并时可消去全部变量，结果为 <code>1</code>。</p>
<p><strong>用卡诺图化简法求最简与或表达式的步骤：</strong></p>
<ol>
<li>画出函数的卡诺图；</li>
<li>合并最小项；</li>
<li>写出最简与或表达式。</li>
</ol>
<p><img src="https://pic.tyzhang.top/images/2020/12/11/Snipaste_2020-12-11_16-21-57.png" alt="Snipaste_2020-12-11_16-21-57.png"><br>
<img src="https://pic.tyzhang.top/images/2020/12/11/Snipaste_2020-12-11_16-22-49.png" alt="Snipaste_2020-12-11_16-22-49.png"></p>
<p><strong>提示：</strong></p>
<ul>
<li>圈的个数应尽可能少。即保证 <code>1</code> 格一个也不漏圈的前提下，圈的个数越少越好。</li>
<li>按照 <code>2k</code> 个方格来组合，即圈内的 <code>1</code> 格数必须为 <code>1,2,4,8</code> 等，圈的面积越大越好。</li>
<li>每个圈应至少包含一个新的 <code>1</code> 格，否则这个图是多余的。</li>
<li>用卡诺图化简得到的最简与或式不是唯一的。</li>
</ul>
<p>至此，我们已经明白了卡诺图的用法。</p>

                
                <hr>
                <!-- Pager -->
                <ul class="pager">
                    
                        <li class="previous">
                            <a href="/article/Java中的移位运算符/" data-toggle="tooltip" data-placement="top" title="Java中的移位运算符：<<,>>,>>> ">&larr; 上一篇</a>
                        </li>
                    
                    
                        <li class="next">
                            <a href="/article/jdk学习之路—反射/" data-toggle="tooltip" data-placement="top" title="浅谈反射">下一篇 &rarr;</a>
                        </li>
                    
                </ul>

                <br>

                <!--打赏-->
                
                <!--打赏-->

                <br>
                <!--分享-->
                
                <!--分享-->
                <br>                       
                
                <!-- require APlayer -->
                
            </div>
            
            <!-- Tabe of Content -->
            <!-- Table of Contents -->

  
    <style>
      span.toc-nav-number{
        display: none
      }
    </style>
  
    
      <aside id="sidebar">
        <div id="toc" class="toc-article">
        <strong class="toc-title">目录</strong>
        
          <ol class="toc-nav"><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#只出现一次的数字问题"><span class="toc-nav-number">1.</span> <span class="toc-nav-text">&#x53EA;&#x51FA;&#x73B0;&#x4E00;&#x6B21;&#x7684;&#x6570;&#x5B57;&#x95EE;&#x9898;</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#只出现一次的数字-ii"><span class="toc-nav-number">1.1.</span> <span class="toc-nav-text">&#x53EA;&#x51FA;&#x73B0;&#x4E00;&#x6B21;&#x7684;&#x6570;&#x5B57; II</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-4"><a class="toc-nav-link" href="#卡诺图解法"><span class="toc-nav-number">1.1.1.</span> <span class="toc-nav-text">&#x5361;&#x8BFA;&#x56FE;&#x89E3;&#x6CD5;</span></a></li><li class="toc-nav-item toc-nav-level-4"><a class="toc-nav-link" href="#逻辑真值表达式解法"><span class="toc-nav-number">1.1.2.</span> <span class="toc-nav-text">&#x903B;&#x8F91;&#x771F;&#x503C;&#x8868;&#x8FBE;&#x5F0F;&#x89E3;&#x6CD5;</span></a></li></ol></li></ol></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#卡诺图"><span class="toc-nav-number">2.</span> <span class="toc-nav-text"><span id="jump">&#x5361;&#x8BFA;&#x56FE;</span></span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#关于最小项"><span class="toc-nav-number">2.1.</span> <span class="toc-nav-text">&#x5173;&#x4E8E;&#x201C;&#x6700;&#x5C0F;&#x9879;&#x201D;</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-4"><a class="toc-nav-link" href="#1最小项的定义"><span class="toc-nav-number">2.1.1.</span> <span class="toc-nav-text">&#xFF08;1&#xFF09;&#x6700;&#x5C0F;&#x9879;&#x7684;&#x5B9A;&#x4E49;</span></a></li><li class="toc-nav-item toc-nav-level-4"><a class="toc-nav-link" href="#2最小项的表示方法"><span class="toc-nav-number">2.1.2.</span> <span class="toc-nav-text">&#xFF08;2&#xFF09;&#x6700;&#x5C0F;&#x9879;&#x7684;&#x8868;&#x793A;&#x65B9;&#x6CD5;</span></a></li><li class="toc-nav-item toc-nav-level-4"><a class="toc-nav-link" href="#3最小项的性质"><span class="toc-nav-number">2.1.3.</span> <span class="toc-nav-text">&#xFF08;3&#xFF09;&#x6700;&#x5C0F;&#x9879;&#x7684;&#x6027;&#x8D28;</span></a></li><li class="toc-nav-item toc-nav-level-4"><a class="toc-nav-link" href="#4逻辑函数的最小项表达式"><span class="toc-nav-number">2.1.4.</span> <span class="toc-nav-text">&#xFF08;4&#xFF09;&#x903B;&#x8F91;&#x51FD;&#x6570;&#x7684;&#x6700;&#x5C0F;&#x9879;&#x8868;&#x8FBE;&#x5F0F;</span></a></li><li class="toc-nav-item toc-nav-level-4"><a class="toc-nav-link" href="#5公式和定理"><span class="toc-nav-number">2.1.5.</span> <span class="toc-nav-text">&#xFF08;5&#xFF09;&#x516C;&#x5F0F;&#x548C;&#x5B9A;&#x7406;</span></a></li><li class="toc-nav-item toc-nav-level-4"><a class="toc-nav-link" href="#6最小项的相邻性"><span class="toc-nav-number">2.1.6.</span> <span class="toc-nav-text">&#xFF08;6&#xFF09;&#x6700;&#x5C0F;&#x9879;&#x7684;&#x76F8;&#x90BB;&#x6027;</span></a></li></ol></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#卡诺图的构成"><span class="toc-nav-number">2.2.</span> <span class="toc-nav-text">&#x5361;&#x8BFA;&#x56FE;&#x7684;&#x6784;&#x6210;</span></a></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#逻辑函数的卡诺图化简法"><span class="toc-nav-number">2.3.</span> <span class="toc-nav-text">&#x903B;&#x8F91;&#x51FD;&#x6570;&#x7684;&#x5361;&#x8BFA;&#x56FE;&#x5316;&#x7B80;&#x6CD5;</span></a></li></ol></li></ol>
        
        </div>
      </aside>
    

                
            <!-- Sidebar Container -->
            <div class="
                col-lg-8 col-lg-offset-2
                col-md-10 col-md-offset-1
                sidebar-container">

                <!-- Featured Tags -->
                
                <section>
                    <!-- no hr -->
                    <h5><a href="/tags/">标签</a></h5>
                    <div class="tags">
                       
                          <a class="tag" href="/tags/#algorithm" title="algorithm">algorithm</a>
                        
                    </div>
                </section>
                

                <!-- Friends Blog -->
				<!--
                
                <hr>
                <h5>朋友们</h5>
                <ul class="list-inline">

                    
                        <li><a href="https://tyzhang.top/" target="_blank">ztygalaxy</a></li>
                    
                        <li><a href="http://www.yctang.club/" target="_blank">yctang</a></li>
                    
                        <li><a href="https://dolnw.github.io" target="_blank">JCWang</a></li>
                    
                </ul>
                
				-->
            </div>
        </div>
    </div>
</article>


<!-- async load function -->
<script>
    function async(u, c) {
      var d = document, t = 'script',
          o = d.createElement(t),
          s = d.getElementsByTagName(t)[0];
      o.src = u;
      if (c) { o.addEventListener('load', function (e) { c(null, e); }, false); }
      s.parentNode.insertBefore(o, s);
    }
</script>
<!-- anchor-js, Doc:http://bryanbraun.github.io/anchorjs/ -->
<script>
    async("https://cdn.bootcss.com/anchor-js/1.1.1/anchor.min.js",function(){
        anchors.options = {
          visible: 'hover',
          placement: 'left',
          icon: ''
        };
        anchors.add().remove('.intro-header h1').remove('.subheading').remove('.sidebar-container h5');
    })
</script>
<style>
    /* place left on bigger screen */
    @media all and (min-width: 800px) {
        .anchorjs-link{
            position: absolute;
            left: -0.75em;
            font-size: 1.1em;
            margin-top : -0.1em;
        }
    }
</style>


<!-- chrome Firefox 中文锚点定位失效-->
<script src="https://cdn.bootcss.com/jquery/3.3.1/jquery.js"></script>
<!-- smooth scroll behavior polyfill  -->
<script type="text/javascript" src="/js/smoothscroll.js"></script>
<script>
        $('#toc').on('click','a',function(a){
            // var isChrome = window.navigator.userAgent.indexOf("Chrome") !== -1;
            // console.log(window.navigator.userAgent,isChrome)
                // if(isChrome) {
                    // console.log(a.currentTarget.outerHTML);
                    // console.log($(a.currentTarget).attr("href"));
                    //跳转到指定锚点
                    // document.getElementById(a.target.innerText.toLowerCase()).scrollIntoView(true);
                    document.getElementById($(a.currentTarget).attr("href").replace("#","")).scrollIntoView({behavior: 'smooth' });
                // }
        })  
</script>


    <!-- Footer -->
    <!-- Footer -->
<footer>
    <div class="container">
        <div class="row">
            <div class="col-lg-8 col-lg-offset-2 col-md-10 col-md-offset-1">
                <ul class="list-inline text-center">
                
                
                
				
                

                

                
                    <li>
                        <a target="_blank"  href="https://github.com/songzblink">
                            <span class="fa-stack fa-lg">
                                <i class="fa fa-circle fa-stack-2x"></i>
                                <i class="fa fa-github fa-stack-1x fa-inverse"></i>
                            </span>
                        </a>
                    </li>
                

                

                </ul>
                <p class="copyright text-muted">
                    Copyright &copy; 宋正兵 2021 
                    <br>
                    Theme by <a href="http://www.huweihuang.com">Huwei Huang</a>
                    re-Ported by <a href="https://github.com/ztygalaxy">ztygalaxy</a>
					
                </p>
            </div>
        </div>
    </div>
</footer>

<!-- jQuery -->
<script src="/js/jquery.min.js"></script>

<!-- Bootstrap Core JavaScript -->
<script src="/js/bootstrap.min.js"></script>

<!-- Custom Theme JavaScript -->
<script src="/js/hux-blog.min.js"></script>


<!-- async load function -->
<script>
    function async(u, c) {
      var d = document, t = 'script',
          o = d.createElement(t),
          s = d.getElementsByTagName(t)[0];
      o.src = u;
      if (c) { o.addEventListener('load', function (e) { c(null, e); }, false); }
      s.parentNode.insertBefore(o, s);
    }
</script>

<!-- 
     Because of the native support for backtick-style fenced code blocks 
     right within the Markdown is landed in Github Pages, 
     From V1.6, There is no need for Highlight.js, 
     so Huxblog drops it officially.

     - https://github.com/blog/2100-github-pages-now-faster-and-simpler-with-jekyll-3-0  
     - https://help.github.com/articles/creating-and-highlighting-code-blocks/    
-->
<!--
    <script>
        async("http://cdn.bootcss.com/highlight.js/8.6/highlight.min.js", function(){
            hljs.initHighlightingOnLoad();
        })
    </script>
    <link href="http://cdn.bootcss.com/highlight.js/8.6/styles/github.min.css" rel="stylesheet">
-->


<!-- jquery.tagcloud.js -->
<script>
    // only load tagcloud.js in tag.html
    if($('#tag_cloud').length !== 0){
        async("zbsong.top/js/jquery.tagcloud.js",function(){
            $.fn.tagcloud.defaults = {
                //size: {start: 1, end: 1, unit: 'em'},
                color: {start: '#bbbbee', end: '#0085a1'},
            };
            $('#tag_cloud a').tagcloud();
        })
    }
</script>

<!--fastClick.js -->
<script>
    async("https://cdn.bootcss.com/fastclick/1.0.6/fastclick.min.js", function(){
        var $nav = document.querySelector("nav");
        if($nav) FastClick.attach($nav);
    })
</script>


<!-- Google Analytics -->




<!-- Baidu Tongji -->






	<a id="rocket" href="#top" class=""></a>
	<script type="text/javascript" src="/js/totop.js?v=1.0.0" async=""></script>
    <script type="text/javascript" src="/js/toc.js?v=1.0.0" async=""></script>
<!-- Image to hack wechat -->
<img src="zbsong.top/img/icon_wechat.png" width="0" height="0" />
<!-- Migrate from head to bottom, no longer block render and still work -->

<script type="text/x-mathjax-config">
    MathJax.Hub.Config({
        tex2jax: {
            inlineMath: [ ["$","$"], ["\\(","\\)"] ],
            skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code'],
            processEscapes: true
        }
    });
    MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax();
        for (var i = 0; i < all.length; ++i)
            all[i].SourceElement().parentNode.className += ' has-jax';
    });
</script>
<!--
<script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
-->
<script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-MML-AM_CHTML"></script>
</body>

</html>
